import java.util.Arrays;

public class plbench_sort {
	private static final int TEST_SIZE = 10000000;
	private static final int TEST_MAX_VALUE = 1000000000;

	public static void main(String[] args) {
		int[] testVec = generateTestVec();
		myMergeSort(testVec);
		System.out.println(computeOutputHash(testVec));
	}

	private static int[] generateTestVec() {
		int[] testVec = new int[TEST_SIZE];
		long rand = 0;

		for (int i = 0; i < TEST_SIZE; i++) {
			testVec[i] = (int)rand;
			rand *= 131313131;
			rand += 13131;
			rand %= TEST_MAX_VALUE;
		}
		return testVec;
	}

	private static int computeOutputHash(int[] testVec) {
		long hash = testVec.length;
		for (int v : testVec)
			hash = (hash * 131313131 + v) % TEST_MAX_VALUE;
		return (int)hash;
	}

	private static void myMergeSort(int[] elements) {
		if (elements.length > 1) {
			int mid = elements.length / 2;
			int[] subSlice1 = Arrays.copyOf(elements, mid);
			int[] subSlice2 = Arrays.copyOfRange(elements, mid, elements.length);

			myMergeSort(subSlice1);
			myMergeSort(subSlice2);

			int elementLen = elements.length;
			int subLen1 = subSlice1.length;
			int subLen2 = subSlice2.length;

			while (subLen1 > 0 && subLen2 > 0) {
				if (subSlice1[subLen1 - 1] < subSlice2[subLen2 - 1])
					elements[--elementLen] = subSlice2[--subLen2];
				else
					elements[--elementLen] = subSlice1[--subLen1];
			}
			if (subLen1 > 0)
				System.arraycopy(subSlice1, 0, elements, elementLen - subLen1, subLen1);
			else
				System.arraycopy(subSlice2, 0, elements, elementLen - subLen2, subLen2);
		}
	}
}
